package Sort;

import java.util.ArrayDeque;
import java.util.Deque;

public class Sort {
    /**
     * 时间复杂度 O(N^2)
     * 最坏情况下：逆序的： 5 4 3 2 1
     * 最好情况下：有序的：1 2 3 4 5 O（N）
     * 如果数据越有序，直接插入排序越快
     * 空间复杂度 ： O(1)
     * 稳定性：稳定的排序
     * 本身如果是一个稳定的排序，那么可以实现为不稳定的
     * 但是，如果一个排序 本身就是不稳定的，能实现为稳定的吗？  不能
     * @param arr
     */
    public  static  void insetSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp =arr[i];
            int j=i-1;
            for (;j>=0;j--){
                if(arr[j]>tmp){
                    arr[j+1] =arr[j];
                }else{
                    arr[j+1] =tmp;
                    break;
                }
            }
            arr[j+1]  = tmp;
        }


    }

    /**
     * 时间复杂度：n^1.3~n^1.5
     * 空间复杂度： O(1)
     * 稳定性：不稳定的
     * @param array
     */
    public  static void shellSort(int[] array){
        int gap = array.length;
        while(gap >1){
            gap /= 2;
            //gap = gap/3+1;
            shell(array,gap);
        }
    }
    private static  void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j =i-gap;
            for (;j>=0;j-=gap){
                if (array[j]>tmp){
                    array[j+gap] = array[j];
                }else{
                    array[j+gap] =tmp;
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    //选择排序

    /**
     *时间复杂度：O(N^2); 和数据是否有序无关
     * 空间复杂度：O(1)
     * 稳定性：不稳定的排序
     * @param array
     */
    public  static void selectSort2(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j=i+1;j<array.length;j++){
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    private  static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public  static void selectSort(int[] array){
        int left = 0;
        int right = array.length-1;
        while (left<right){
            int minIndex = left;
            int maxIndex = right;
            for (int i = left+1; i <=right ; i++) {
                if (array[i]<array[minIndex]){
                    minIndex = i;
                }
                if (array[i]>array[maxIndex]){
                    maxIndex = i;
                }
            }
            swap(array,left,minIndex);
            if (maxIndex==left){
                maxIndex=minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }
    //堆排序

    /**
     * 时间复杂度都:O(N*log2N)
     * 空间复杂度:O(1)
     * 稳定性：不稳定
     * @param array
     */
    public  static  void heapSort(int[] array){
        createHeap(array);
        int end = array.length-1;
        while (end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }
    private static void createHeap(int[] array){
        for (int parent = (array.length-1-1)/2;parent>=0;parent--){
            siftDown(array,parent,array.length);
        }
    }

    /**
     *
     * @param array
     * @param parent 每棵子树调整的根节点
     * @param length 每棵子树调整的结束节点
     */
    private static void siftDown(int[] array,int parent,int length){
        int child = 2*parent+1;
        while(child<length){
            if(child+1<length&&array[child]<array[child+1]){
                child++;
            }
            if (array[child]>array[parent]){
                swap(array,parent,child);
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }
    //冒泡排序

    /**
     * 时间复杂度： 【讨论 没有优化的情况下，也就是说， 没有下方的 boolean元素和-i操作】
     *               O(N^2)
     *               优化以后，可能会达到O(N)
     *空间复杂度：O（1）
     * 稳定性：稳定的排序
     * @param array
     */
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j=i-1;j<array.length-1-i;j++){
                if (array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if (!flg){
                break;
            }
        }
    }
    //快速排序

    /**
     * 时间复杂度都:
     *           最坏情况： 当数据为 1 2 3 4 5 6.……有序的情况，确实是O(N^2)
     *                            6 5 4 3 2 1
     *           最好情况： O(N*logN)
     * 空间复杂度: 最坏情况：O(N);
     *           最好情况：O(logN)
     * 稳定性: 不稳定
     * @param array
     */
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    //非递归实现快速排序
    public static  void quickNor(int[] array,int start,int end){
        Deque<Integer> stack = new ArrayDeque<>();
        int pivot = partition(array,start,end);
        if(pivot>start+1){
            stack.push(start);
            stack.push(pivot-1);
        }
        if (pivot<end-1){
            stack.push(pivot+1);
            stack.push(end);
        }
        while (!stack.isEmpty()){
            end =stack.pop();
            start = stack.poll();
            pivot = partition(array,start,end);
            if(pivot>start+1){
                stack.push(start);
                stack.push(pivot-1);
            }
            if (pivot<end-1){
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }
    //优化版
    private static void quick(int[] array,int start,int end){
        if (start>=end){
            return;
        }
        if (end-start +1 <= 10){
            insertSortRange(array,start,end);
            return;
        }
        //System.out.println("start:  "+start+"end:" +end);
        int midIndex = getMiddleNum(array,start,end);
        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    public static void  insertSortRange(int[] array,int start,int end){
        for (int i = start; i <=end ; i++) {
            int tmp =array[i];
            int j =i-1;
            for (;j>=start;j--){
                if(array[j]>tmp){
                    array[j+1] =array[j];
                }else {
                    array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    public static int getMiddleNum(int[] array,int left,int right){
        int mid =(left+right)/2;
        if (array[left]<array[right]){
            if(array[left]<array[right]){
                return left;
            } else if (array[mid]>array[right]) {
                return right;
            }else {
                return mid;
            }
        } else{
            if (array[mid]>array[left]){
                return left;
            } else if (array[mid]<array[right]) {
                return right;
            }else {
                return mid;
            }
        }

    }
    private static void quick1(int[] array,int start,int end){
        if (start>=end){
            return;
        }

        int midIndex = getMiddleNum(array,start,end);
        int pivot = partition(array,start,end);
        quick1(array,start,pivot-1);
        quick1(array,pivot+1,end);
    }
    //挖坑法
    public static int partition(int[] array,int left,int right){
        int tmp = array[left];
        while (left<right){
            while (left<right&&array[right]>=tmp){
                right--;
            }
            array[left] = array[right];
            while (left<right&&array[left]<=tmp){
                left++;
            }
            array[right]= array[left];
        }
        array[left] = tmp;
        return left;
    }

    //前后指针法
    private static  int partitionP(int[] array,int left,int right){
        int prev = left;
        int cur = left+1;
        while (left<right){
            if(array[cur]<array[left]&&array[++prev] !=array[cur]){
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }



    //hoare法
    private static int partitionHare(int[] array,int left,int right){
        int tmp =  array[left];
        int tmpLeft = left;
        while(left<right){
            while (left<right&&array[right]>=tmp){
                right --;
            }
            while (left<right&&array[left]<=tmp){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,tmpLeft);
        return left;
    }

    /**
     * 归并排序
     * 时间复杂度:O(N*logN)
     * 空间复杂度:O(N)
     * 稳定性:稳定的排序
     * @param array
     */
    public static  void mergeSort(int[] array){
        mergeSortTmp(array,0,array.length-1);
    }
    public static  void mergeSortTmp(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int mid =(left+right)/2;
        mergeSortTmp(array,left,mid);
        mergeSortTmp(array,mid+1,right);
        //写道这里，全部分解完毕了，
        //开始合并
        merge(array,left,mid,right);
    }
    private static void merge(int[] array,int left,int mid,int right){
        int[] tmp =new int[right-left+1];
        int k =0;
        int s1 = left;
        int s2 =mid+1;
        while (s1<=mid&&s2<=right){
            if (array[s1]<array[s2]){
                tmp[k++] =array[s1++];
            }else{
                tmp[k++] =array[s2++];
            }
        }
        while (s1<=mid){
            tmp[k++] =array[s1++];
        }
        while (s2<=right){
            tmp[k++] =array[s2++];
        }
        //可以保证tmp数组，是有序数列
        for (int i=0;i<k;i++){
            array[i+left] =tmp[i];
        }
    }

    /**
     * 非递归实现，归并排序
     * @param array
     */
    public static void mergeSortNor(int[] array){
        int gap =1;
        while (gap<array.length){
            for (int i = 0; i < array.length; i=i+gap*2) {
                int left =i;
                int mid =left+gap-1;
                if (mid>=array.length){
                    mid = array.length-1;
                }
                int right = mid+gap;
                if (right>=array.length){
                    right = array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap*=2;
        }
    }

    /**
     * 计数排序
     * 时间复杂度 O(范围+n)
     *            范围越大， 越慢
     * 空间复杂度  O(范围)
     * @param array
     */
    public  static void countSort(int[] array){
        //1/找最大值和最小值 来确定 计数数组的大小
        int minVal =array[0];
        int maxVal =array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i]<minVal){
                minVal = array[i];
            }
            if (array[i]>maxVal){
                maxVal=array[i];
            }
        }
        int len =maxVal-minVal+1;
        int[] count =new int[len];
        //2.遍历原来的数组array 把 每个元素 放到对应的计数数组中，进行计数
        for (int i = 0; i < array.length; i++) {
            int index = array[i];
            count[index-minVal]++;
        }
        //依次 遍历计数数组0（范围）
        int index =0;
        for (int i = 0; i < count.length; i++) {
            while (count[i]!=0){
                array[index] = i+minVal;
                index++;
                count[i]--;
            }
        }
    }
}
